package 题目集.bfs.多源bfs;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。
 * 请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。
 * 我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。
 * https://leetcode.cn/problems/as-far-from-land-as-possible/description/
 */
public class ch01_地图分析 {
    /**
     * 思路：从所有陆地进行bfs，最后一次bfs的深度即为最远的海洋距离
     */
    static final int N = 101;
    static final int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static final int[][] queue = new int[N * N][2];    //队列的最大长度n*n

    public int maxDistance(int[][] grid) {
        int n = grid.length;
        int head = 0, tail = 0;
        for (int i = 0; i < n; i++) {   //将所有陆地加入队列
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    queue[tail][0] = i;
                    queue[tail++][1] = j;
                }
            }
        }
        if (tail == 0 || tail == n * n) return -1;    //如果只有陆地或者海洋
        int step = 0;
        while (head < tail) {
            step++;
            int size = tail;
            while (head < size) {
                int[] pop = queue[head++];
                for (int[] d : dir) {
                    int x = pop[0] + d[0];
                    int y = pop[1] + d[1];
                    if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 0) {
                        queue[tail][0] = x;
                        queue[tail][1] = y;
                        grid[x][y] = 1; //标记为已走过
                        tail++;
                    }
                }
            }
        }
        return step - 1;    //减一是因为起点也会加一次
    }

    @Test
    public void test() {
        System.out.println(maxDistance(new int[][]{{1, 1, 1}, {1, 1, 1}, {1, 1, 1}}));
    }
}
